import java.util.ArrayList;
import java.util.List;

/**
 * @program: LeetCode
 * @description: LeetCode : 6346. 打家劫舍 IV
 * @author: WXY
 * @create: 2023-02-05 11:02
 * @Version 1.0
 **/
public class Num6346_minCapability {
    public static int minCapability1(int[] arr, int k) {
        int start = arr[0];
        int end = arr[0];
        for (int i = 1; i < arr.length; i++) {
            start = Math.min(arr[i], start);
            end = Math.max(arr[i], end);
        }
        while (start < end) {
            int mid = (start + end) >> 1;
            if (check(arr, k, mid)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }

    private static boolean check(int[] arr, int k, int mid) {
        int l = -2;
        int r = 0;
        int count = 0;
        while (r < arr.length) {
            if (r > l + 1 && arr[r] <= mid) {
                count++;
                l = r;
            }
            r++;
        }
        return count >= k;
    }

    static List<Integer> list = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();

    public static int minCapability(int[] arr, int k) {
        int len = arr.length;
        boolean[] used = new boolean[arr.length];
        process(arr, 0, 0, used,k);
        int min = Integer.MAX_VALUE;
        for (int num : list) {
            min = Math.min(num, min);
        }
        return min;
    }

    private static void process(int[] arr, int index, int count,boolean[] used,int k) {
        if (k == count) {
            int max = 0;
            for (int num : path) {
                max = Math.max(max, num);
            }
            list.add(max);
            return;
        }
        for (int i = index; i < arr.length; i++) {
            if (i > 0 && used[i - 1] == true)continue;
            path.add(arr[i]);
            used[i] = true;
            count++;
            process(arr, i + 1, count,used, k);
            count--;
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,7,9,3,1};
        int k = 2;
        int i = minCapability1(arr, k);
        System.out.println(i);

    }
}
